/**
 * Java implementation of a Node of type T for four different binary trees:
 *      1.) Binary Search Tree
 *      2.) AVL Tree
 *      3.) Red-Black Tree
 *      4.) Splay Tree
 * These trees all use the same node for ease of implementation.
 * 
 * @author Jonathan E. Landrum <me@jonlandrum.com>
 * @since 2016-01-04
 */

package com.jonlandrum.selfbalancingtree;

public class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
    /*
     * Instance variables
     */
    protected T data = null;
    protected int leftHeight = 0;
    protected int rightHeight = 0;
    protected Color color = Color.BLACK;
    
    /*
     * Object pointers
     */
    protected Node<T> parent = null;
    protected Node<T> leftChild = null;
    protected Node<T> rightChild = null;
    
    /*
     * Color enumeration
     */
    protected enum Color {
        RED, BLACK;
    }
    
    public void swapColor() {
        color = Color.values()[color.ordinal() ^ 1];
    }
    
    /*
     * Constructors
     */
    public Node() {}
    
    public Node(T d) {
        data = d;
    }
    
    public Node(Node<T> n) {
        data = n.getData();
    }
    
    /*
     * Setters
     */
    public void setData(T d) {
        data = d;
    }
    
    public void setData(Node<T> n) {
        data = n.getData();
    }
    
    public void setLeftHeight(int h) {
        leftHeight = h;
    }
    
    public void setRightHeight(int h) {
        rightHeight = h;
    }
    
    public void setParent(Node<T> n) {
        parent = n;
    }
    
    public void setLeftChild(Node<T> n) {
        leftChild = n;
    }
    
    public void setRightChild(Node<T> n) {
        rightChild = n;
    }
    
    /*
     * Getters
     */
    public T getData() {
        return data;
    }
    
    public int getLeftHeight() {
        return leftHeight;
    }
    
    public int getRightHeight() {
        return rightHeight;
    }
    
    public int getHeight() {
        return (Math.max(this.getLeftHeight(), this.getRightHeight()));
    }
    
    public int getBalance() {
        return (this.getRightHeight() - this.getLeftHeight());
    }
    
    public int getColor() {
        return color.ordinal();
    }
    
    public int getBlackHeight() {
        if (this.isEmpty()) { return 1; }
        int result = this.getColor();
        if (this.hasLeftChild()) {
            result += this.getLeftChild().getBlackHeight();
        } else if (this.hasRightChild()) {
            result += this.getRightChild().getBlackHeight();
        } else {
            result += 1;
        }
        return result;
    }
    
    public Node<T> getParent() {
        return parent;
    }
    
    public Node<T> getSibling() {
        Node<T> result = new Node<T>();
        if (this.isLeftChild() && this.getParent().hasRightChild()) {
            result = this.getParent().getRightChild();
        } else if (this.isRightChild() && this.getParent().hasLeftChild()) {
            result = this.getParent().getLeftChild();
        }
        return result;
    }
    
    public Node<T> getLeftChild() {
        return leftChild;
    }
    
    public Node<T> getRightChild() {
        return rightChild;
    }
    
    public int getNumChildren() {
        int children = 0;
        if (this.hasLeftChild() && !this.getLeftChild().isEmpty()) {
            children += 1 + this.getLeftChild().getNumChildren();
        }
        if (this.hasRightChild() && !this.getRightChild().isEmpty()) {
            children += 1 + this.getRightChild().getNumChildren();
        }
        return children;
    }
    
    /*
     * Booleans
     */
    public boolean isEmpty() {
        return data == null;
    }
    
    public boolean isRoot() {
        return parent == null;
    }
    
    public boolean isLeaf() {
        return (!this.hasLeftChild() && !this.hasRightChild());
    }
    
    public boolean isLeftChild() {
        return this.hasParent() && this.getParent().hasLeftChild() &&
            this == this.getParent().getLeftChild();
    }
    
    public boolean isRightChild() {
        return this.hasParent() && this.getParent().hasRightChild() && this ==
            this.getParent().getRightChild();
    }
    
    public boolean hasParent() {
        return parent != null;
    }
    
    public boolean hasSibling() {
        return this.getSibling().getData() != null;
    }
    
    public boolean hasLeftChild() {
        return leftChild != null && !leftChild.isEmpty();
    }
    
    public boolean hasRightChild() {
        return rightChild != null && !rightChild.isEmpty();
    }
    
    public boolean hasOneChild() {
        return ((this.hasLeftChild() && !this.hasRightChild()) ||
            (!this.hasLeftChild() && this.hasRightChild()));
    }
    
    /*
     * Operations
     */
    @Override
    public String toString() {
        return this.getData() == null ? "" : this.getData().toString();
    }
    
    @Override
    public int compareTo(Node<T> that) {
        return this.getData().compareTo(that.getData());
    }
}